/*
题目：把二叉搜索树转换成累加树
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），
使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
https://leetcode.cn/problems/convert-bst-to-greater-tree/
 */
public class ConvertBST {
    public TreeNode convertBST(TreeNode root) {
        TreeNode ret = root;
        int curVal = 0;

        while (root != null) {
            TreeNode rootRight = root.right;
            if (rootRight != null) {
                while (rootRight.left != null && rootRight.left != root) {
                    rootRight = rootRight.left;
                }
                if (rootRight.left == null) { //如果还没线索化
                    rootRight.left = root;
                    root = root.right;
                } else {  //如果已经线索化了
                    root.val += curVal;
                    curVal = root.val;

                    root = root.left;  //往线索化后的左边走，也就是回到当前节点的双亲结点
                    rootRight.left = null;
                }
            } else {
                root.val += curVal;
                curVal = root.val;

                root = root.left;
            }
        }

        return ret;
    }
}
